package main;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定两个字符串s和t，请判断它们是不是一组变位词。如“abc”和”cba“
 */
public class IsAnagram {
    public static void main(String[] args) {
        String str1 = "abcc";
        String str2 = "cabc";
        // boolean flag = new IsAnagram().isAnagram(str1,str2);
        boolean flag = new IsAnagram().isAnagram2(str1,str2);
        if (flag) {
            System.out.println("is anagram");
        } else {
            System.out.println("is not anagram");
        }
    }

    /*
    由于字符串只包含英文小写字母情形，可以用数组模拟哈希表
    时间复杂度为n，空间复杂度为1
     */
    public boolean isAnagram(String str1,String str2){
        if (str1.length() != str2.length()){
            return false;
        }
        int[] countArr = new int[26];
        for (char c : str1.toCharArray()){
            countArr[c - 'a']++;
        }
        for (char c : str2.toCharArray()){
            if (countArr[c - 'a'] == 0){
                return false;
            }
            countArr[c - 'a']--;
        }
        return true;
    }
    /*
    若可为任意字符，unicode编码下65536的数组似乎太浪费空间
    用真正哈希表(time:n,space:n)
     */
    public boolean isAnagram2(String str1,String str2){
        if (str1.length() != str2.length()){
            return false;
        }
        Map<Character,Integer> counts = new HashMap<>();
        for (char ch : str1.toCharArray()){
            counts.put(ch,counts.getOrDefault(ch,0) + 1);
        }
        for (char ch : str2.toCharArray()){
            if (!counts.containsKey(ch) || counts.get(ch) == 0){
                return false;
            }
            counts.put(ch,counts.get(ch) - 1);
        }
        return true;
    }

}
